翻訳と辞書 Words near each other ・ Lensky ・ Lensky (rural locality) ・ Lensky District ・ Lensky District, Arkhangelsk Oblast ・ Lensky District, Sakha Republic ・ Lensless glasses ・ Lenslet ・ Lenslok ・ Lensman (disambiguation) ・ Lensman (game) ・ Lensman series ・ Lensmann ・ Lensmeter ・ Lenstra ・ Lenstra elliptic curve factorization ・ Lenstra–Lenstra–Lovász lattice basis reduction algorithm ・ Lensvik ・ Lensvik Church ・ Lenswood ・ Lenswood wine sub-region ・ Lenswood, South Australia ・ Lensworld.eu-Zannata ・ Lensy Debboudt ・ Lent ・ Lent (album) ・ Lent (disambiguation) ・ Lent Bumps ・ Lent Bumps 1998 ・ Lent Bumps 1999 ・ Lent Bumps 2000 Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Lenstra–Lenstra–Lovász lattice basis reduction algorithm ： ウィキペディア英語版 Lenstra–Lenstra–Lovász lattice basis reduction algorithm The Lenstra–Lenstra–Lovász (LLL) lattice basis reduction algorithm is a polynomial time lattice reduction algorithm invented by Arjen Lenstra, Hendrik Lenstra and László Lovász in 1982. Given a basis $\backslash mathbf=\backslash \_2,\; \backslash dots,\; \backslash mathbf\_d\; \backslash \}$ with ''n''-dimensional integer coordinates, for a lattice L (a discrete subgroup of R''n'') with $\backslash \; d\; \backslash leq\; n$, the LLL algorithm calculates an ''LLL-reduced'' (short, nearly orthogonal) lattice basis in time :$O(d^5n\backslash log^3\; B)\backslash ,$ where B is the largest length of $b\_i$ under the Euclidean norm. The original applications were to give polynomial-time algorithms for factorizing polynomials with rational coefficients, for finding simultaneous rational approximations to real numbers, and for solving the integer linear programming problem in fixed dimensions. ==LLL reduction== The precise definition of LLL-reduced is as follows: Given a basis :$\backslash mathbf=\backslash \_1,\; \backslash dots,\; \backslash mathbf\_n\; \backslash \},$ define its Gram–Schmidt process orthogonal basis :$\backslash mathbf^$ *=\^ *_1, \dots, \mathbf^ *_n \}, and the Gram-Schmidt coefficients :$\backslash mu\_=\backslash frac^$ *_j\rangle}^ *_j\rangle}, for any . Then the basis $B$ is LLL-reduced if there exists a parameter $\backslash delta$ in (0.25,1] such that the following holds: # (size-reduced) For . By definition, this property guarantees the length reduction of the ordered basis. # (Lovász condition) For k = 1,2,..,n $\backslash colon\; \backslash delta\; \backslash Vert\; \backslash mathbf^$ *_\Vert^2 \leq \Vert \mathbf^ *_k\Vert^2+ \mu_^2\Vert \mathbf^ *_\Vert^2. Here, estimating the value of the $\backslash delta$ parameter, we can conclude how well the basis is reduced. Greater values of $\backslash delta$ lead to stronger reductions of the basis. Initially, A. Lenstra, H. Lenstra and L. Lovász demonstrated the LLL-reduction algorithm for $\backslash delta\; =\; \backslash frac$. Note that although LLL-reduction is well-defined for $\backslash delta\; =\; 1$, the polynomial-time complexity is guaranteed only for $\backslash delta$ in (0.25,1). The LLL algorithm computes LLL-reduced bases. There is no known efficient algorithm to compute a basis in which the basis vectors are as short as possible for lattices of dimensions greater than 4. However, an LLL-reduced basis is nearly as short as possible, in the sense that there are absolute bounds $c\_i\; >\; 1$ such that the first basis vector is no more than $c\_1$ times as long as a shortest vector in the lattice, the second basis vector is likewise within $c\_2$ of the second successive minimum, and so on. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Lenstra–Lenstra–Lovász lattice basis reduction algorithm」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.